public class Test3 {
    //leetcode 44 通配符匹配
    public boolean isMatch(String ss, String pp) {
        //定义状态表示：dp[i][j]表示字符串s[0,i]之间的子串和p[0,j]之间的子串是否匹配
        //状态转移方程：
        //当p[j]为?时，因为?可以匹配任意一个字符，所以dp[i][j] = dp[i-1][j-1]
        //当p[j]为*时，因为*可以匹配任意0个或者任意个数的字符，当*匹配个字符的时候dp[i][j] = dp[i][j-1]
        //当*匹配一个字符的时候dp[i][j] = dp[i-1][j-1],当*匹配两个字符的时候dp[i][j] = dp[i-2][j-1]l...
        //*匹配0个或者任意一个字符成功那么dp[i][j]都为true,匹配0个字符的时候很好表示，但是匹配1，2，3..等
        //字符该怎么办，两种方法：
        //1. dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-2][j-1]...
        // dp[i-1][j] = dp[i-1][j-1] || dp[i-2][j-1]...所以dp[i][j] = dp[i][j-1] || dp[i-1][j]
        //2. dp[i][j] = dp[i][j-1] || dp[i-1][j]，在匹配一个或者多个字符的时候还将*带上
        //当p[j]为字符的时候，dp[i][j] = s[i] == p[j] && dp[i-1][j-1]
        int m = ss.length(), n = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (p[i] == '*') dp[0][i] = true;
            else break;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1;j <= n; j++) {
                if (p[j] == '*') {
                    //第一种表示dp[i][j]的方式
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }else if (p[j] == '?') {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = (s[i] == p[j]) && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
